package com.mystudy.leetcode.problem.tree.p_100;

import com.mystudy.leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 周志龙
 * @Email 15216876513@163.com
 * @Date on 2019/7/25 22:57
 * @Description 相同的树
 */
public class Solution {
    /**
     * 土鳖做法，效率很低
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //使用前序遍历分别遍历两个树
        List<Integer> listP = new ArrayList<>();
        List<Integer> listQ = new ArrayList<>();
        preOrder(p, listP);
        preOrder(q, listQ);
        return listP.equals(listQ);
    }

    public void preOrder(TreeNode node, List list) {
        if (node == null) {
            list.add(null);
            return;
        }
        list.add(node.val);
        preOrder(node.left, list);
        preOrder(node.right, list);
    }

    /**
     * 思考一下，应该是同时遍历两棵树，只要有一个节点不一样，那么就不是同样的树
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p != q) {
            if (p == null || q == null) {
                return false;
            }
        }else{
            return true;
        }
        if (p.val != q.val) {
            return false;
        } else {
            boolean leftEquals = isSameTree2(p.left, q.left);
            boolean rightEquals = isSameTree2(p.right, q.right);
            return leftEquals && rightEquals;
        }


    }

    public void preOrder2(TreeNode p, TreeNode q) {

    }


}
